# !/usr/bin/env python
# -*- coding: utf-8 -*-

#  Reference: https://blog.51cto.com/u_15127575/2901930
#  Usage: Example for solving set covering problem with PuLP.

import pulp

def main():
    SetCoverLP = pulp.LpProblem("SetCover_problem_for_fire_station", sense=pulp.LpMinimize) # 定义模型框架
    zones = list(range(8))
    x = pulp.LpVariable.dicts("zone", zones, cat="Binary") # 定义决策变量
    SetCoverLP += pulp.lpSum([x[j] for j in range(8)])
    reachable = [[1, 0, 0, 0, 0, 0, 0, 0],
                 [0, 1, 1, 0, 0, 0, 0, 0],
                 [0, 1, 1, 0, 1, 0, 0, 0],
                 [0, 0, 0, 1, 0, 0, 0, 0],
                 [0, 0, 0, 0, 1, 0, 0, 0],
                 [0, 0, 0, 0, 0, 1, 1, 0],
                 [0, 0, 0, 0, 0, 0, 1, 1],
                 [0, 0, 0, 0, 0, 0, 1, 1]] # 定义覆盖范围矩阵
    for i in range(8):
        SetCoverLP += pulp.lpSum([x[j]*reachable[j][i] for j in range(8)]) >= 1 # 定义1个区域至少被10分钟距离内的1个消防站覆盖的约束
    SetCoverLP.solve() # 模型计算
    print(SetCoverLP.name)
    temple = "区域 %(zone)d 的决策是：%(status)s"
    if pulp.LpStatus[SetCoverLP.status] == "Optimal":
        for i in range(8):
            output = {'zone': i+1, 'status': '建站' if x[i].varValue else '--'}
            print(temple % output)
    print("需要建立 {} 个消防站。".format(pulp.value(SetCoverLP.objective)))

if __name__ == '__main__':
    main()
